//
//  bistree.c
//  Algorithms - binary search tree AVL树（Adel'son-Vel'skii and Landis）
//
//  Created by YourtionGuo on 04/05/2017.
//  Copyright © 2017 Yourtion. All rights reserved.
//

#include <stdlib.h>
#include <string.h>

#include "bistree.h"

#pragma mark - Private


static void destroy_right(BisTree *tree, BiTreeNode *node);


/**
  执行左旋转

  @param node 二叉树结点
  */
static void rotate_left(BiTreeNode **node)
{
    BiTreeNode    *left, *grandchild;

    left = bitree_left(*node);

    if (((AvlNode *)bitree_data(left))->factor == AVL_LFT_HEAVY) {

        /// 执行 LL ( Left-Left ) 旋转操作

        bitree_left(*node) = bitree_right(left);
        bitree_right(left) = *node;
        ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
        ((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
        *node = left;

    } else {

        /// 执行 LR ( Left-Right ) 旋转操作

        grandchild = bitree_right(left);
        bitree_right(left) = bitree_left(grandchild);
        bitree_left(grandchild) = left;
        bitree_left(*node) = bitree_right(grandchild);
        bitree_right(grandchild) = *node;

        switch (((AvlNode *)bitree_data(grandchild))->factor) {

        case AVL_LFT_HEAVY:

            ((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
            ((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
            break;

        case AVL_BALANCED:

            ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
            ((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
            break;

        case AVL_RGT_HEAVY:

            ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
            ((AvlNode *)bitree_data(left))->factor = AVL_LFT_HEAVY;
            break;

        }

        ((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
        *node = grandchild;
    }

    return;
}


/**
  执行右旋转

  @param node 二叉树结点
  */
static void rotate_right(BiTreeNode **node)
{
    BiTreeNode    *right, *grandchild;

    right = bitree_right(*node);

    if (((AvlNode *)bitree_data(right))->factor == AVL_RGT_HEAVY) {

        /// 执行 RR ( Right-Right ) 旋转操作

        bitree_right(*node) = bitree_left(right);
        bitree_left(right) = *node;
        ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
        ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
        *node = right;

    } else {

        /// 执行 RR ( Right-Right ) 旋转操作

        grandchild = bitree_left(right);
        bitree_left(right) = bitree_right(grandchild);
        bitree_right(grandchild) = right;
        bitree_right(*node) = bitree_left(grandchild);
        bitree_left(grandchild) = *node;

        switch (((AvlNode *)bitree_data(grandchild))->factor) {

        case AVL_LFT_HEAVY:

            ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
            ((AvlNode *)bitree_data(right))->factor = AVL_RGT_HEAVY;
            break;

        case AVL_BALANCED:

            ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
            ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
            break;

        case AVL_RGT_HEAVY:

            ((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
            ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
            break;

        }

        ((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
        *node = grandchild;
    }

    return;
}


/**
  移除由 tree 指定二叉树中 node 的左子结点为根的子树

  @param tree 搜索二叉树
  @param node 指定结点
  */
static void destroy_left(BisTree *tree, BiTreeNode *node)
{
    BiTreeNode    **position;

    /// 不允许在空树中执行移除
    if (bitree_size(tree) == 0) return;

    /// 确定移除结点的位置
    if (node == NULL) {
        position = &tree->root;
    } else {
        position = &node->left;
    }

    /// 移除结点
    if (*position != NULL) {

        destroy_left(tree, *position);
        destroy_right(tree, *position);

        if (tree->destroy != NULL) {
            /// 执行用户指定的 destroy 函数
            tree->destroy(((AvlNode *)(*position)->data)->data);
        }

        /// 清理 AVL 数据结构和结点数据
        free((*position)->data);
        free(*position);
        *position = NULL;

        /// 更新树的 size
        tree->size--;
    }

    return;
}



/**
  移除由 tree 指定二叉树中 node 的右子结点为根的子树

  @param tree 搜索二叉树
  @param node 指定结点
  */
static void destroy_right(BisTree *tree, BiTreeNode *node)
{
    BiTreeNode         **position;

    /// 不允许在空树中执行移除
    if (bitree_size(tree) == 0) return;

    /// 确定移除结点的位置
    if (node == NULL) {
        position = &tree->root;
    } else {
        position = &node->right;
    }

    /// 移除结点
    if (*position != NULL) {

        destroy_left(tree, *position);
        destroy_right(tree, *position);

        if (tree->destroy != NULL) {
            /// 执行用户指定的 destroy 函数
            tree->destroy(((AvlNode *)(*position)->data)->data);
        }

        /// 清理 AVL 数据结构和结点数据
        free((*position)->data);
        free(*position);
        *position = NULL;

        /// 更新树的 size
        tree->size--;
    }

    return;
}


/**
  在 tree 所指定二叉树中插入一个 node 所指定结点

  @param tree 二叉搜索树
  @param node 指定的结点
  @param data 结点数据
  @param balanced 是否已经平衡（已平衡为 1，未平衡为 0）
  @return 插入成功，返回0；已存在，返回1；否则返回-1
  */
static int insert(BisTree *tree, BiTreeNode **node, const void *data, int *balanced)
{
    AvlNode   *avl_data;
    int       cmpval, retval;

    /// 将数据插入到树中

    if (bitree_is_eob(*node)) {

        /// 处理插入空树的情况

        if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL) return -1;

        avl_data->factor = AVL_BALANCED;
        avl_data->hidden = 0;
        avl_data->data = (void *)data;

        return bitree_ins_left(tree, *node, avl_data);

    } else {

        /// 处理非空树情况

        cmpval = tree->compare(data, ((AvlNode *)bitree_data(*node))->data);

        if (cmpval < 0) {

            /// 处理左子树

            if (bitree_is_eob(bitree_left(*node))) {

                if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL) return -1;

                avl_data->factor = AVL_BALANCED;
                avl_data->hidden = 0;
                avl_data->data = (void *)data;

                if (bitree_ins_left(tree, *node, avl_data) != 0) return -1;

                *balanced = 0;

            } else {

                if ((retval = insert(tree, &bitree_left(*node), data, balanced)) != 0) return retval;
            }

            /// 确保树依然保持平衡
            if (!(*balanced)) {

                switch (((AvlNode *)bitree_data(*node))->factor) {

                case AVL_LFT_HEAVY:

                    rotate_left(node);
                    *balanced = 1;
                    break;

                case AVL_BALANCED:

                    ((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
                    break;

                case AVL_RGT_HEAVY:

                    ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                    *balanced = 1;

                }
            }

        } else if (cmpval > 0) {

            /// 处理右子树

            if (bitree_is_eob(bitree_right(*node))) {

                if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
                    return -1;

                avl_data->factor = AVL_BALANCED;
                avl_data->hidden = 0;
                avl_data->data = (void *)data;

                if (bitree_ins_right(tree, *node, avl_data) != 0)
                    return -1;

                *balanced = 0;

            } else {

                if ((retval = insert(tree, &bitree_right(*node), data, balanced)) != 0) return retval;
            }

            /// 确保树依然保持平衡
            if (!(*balanced)) {

                switch (((AvlNode *)bitree_data(*node))->factor) {

                case AVL_LFT_HEAVY:

                    ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                    *balanced = 1;
                    break;

                case AVL_BALANCED:

                    ((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
                    break;

                case AVL_RGT_HEAVY:

                    rotate_right(node);
                    *balanced = 1;

                }
            }

        } else {

            /// 处理找到节点的情况

            ///如果找到非隐藏节点直接返回 1
            if (!((AvlNode *)bitree_data(*node))->hidden) return 1;

            ///插入新数据并取消隐藏
            if (tree->destroy != NULL) {
                /// 销毁隐藏节点的数据
                tree->destroy(((AvlNode *)bitree_data(*node))->data);
            }

            ((AvlNode *)bitree_data(*node))->data = (void *)data;
            ((AvlNode *)bitree_data(*node))->hidden = 0;

            ///如果是隐藏节点数据替换，则不需要再次平衡树
            *balanced = 1;
        }
    }

    return 0;
}


/**
  在 tree 所指定二叉树中隐藏一个 node 所指定结点

  @param tree 二叉搜索树
  @param node 指定的结点
  @param data 结点数据
  @return 成功返回0；否则返回-1
  */
static int hide(BisTree *tree, BiTreeNode *node, const void *data)
{
    int     cmpval, retval;

    /// 没找到节点返回 -1
    if (bitree_is_eob(node)) return -1;

    cmpval = tree->compare(data, ((AvlNode *)bitree_data(node))->data);

    if (cmpval < 0) {

        /// 处理左子树
        retval = hide(tree, bitree_left(node), data);

    } else if (cmpval > 0) {

        /// 处理右子树
        retval = hide(tree, bitree_right(node), data);

    } else {

        /// 将节点标记为隐藏
        ((AvlNode *)bitree_data(node))->hidden = 1;
        retval = 0;
    }

    return retval;
}


/**
  在 tree 所指定二叉搜索树中查找 node 指定的节点

  @param tree 二叉搜索树
  @param node 指定的结点
  @param data 找到的结点数据
  @return 找到返回0；否则返回-1
  */
static int lookup(BisTree *tree, BiTreeNode *node, void **data)
{
    int     cmpval, retval;

    /// 没找到节点返回 -1
    if (bitree_is_eob(node)) return -1;

    cmpval = tree->compare(*data, ((AvlNode *)bitree_data(node))->data);

    if (cmpval < 0) {

        /// 处理左子树
        retval = lookup(tree, bitree_left(node), data);

    } else if (cmpval > 0) {

        /// 处理右子树
        retval = lookup(tree, bitree_right(node), data);

    } else {

        if (!((AvlNode *)bitree_data(node))->hidden) {

            /// 将找到的节点数据返回
            *data = ((AvlNode *)bitree_data(node))->data;
            retval = 0;

        } else {

            /// 没找到节点返回 -1
            return -1;
        }
    }

    return retval;
}

#pragma mark - Public

void bistree_init(BisTree *tree,
                  int (*compare)(const void *key1, const void *key2),
                  void (*destroy)(void *data))
{
    /// 初始化搜索二叉树
    bitree_init(tree, destroy);
    tree->compare = compare;

    return;
}


void bistree_destroy(BisTree *tree)
{
    /// 删除所有树的结点
    destroy_left(tree, NULL);

    /// 清理二叉树数据结构
    memset(tree, 0, sizeof(BisTree));

    return;
}


int bistree_insert(BisTree *tree, const void *data)
{
    int     balanced = 0;
    return insert(tree, &bitree_root(tree), data, &balanced);
}


int bistree_remove(BisTree *tree, const void *data)
{
    return hide(tree, bitree_root(tree), data);
}


int bistree_lookup(BisTree *tree, void **data)
{
    return lookup(tree, bitree_root(tree), data);

}
